Human(s) On The Loop Demand aware Multi Robot Scheduling

Introduction :- The project is an integral part of a Ph.D. thesis led by Ajay Kumar Sandala. It is conducted under the guidance of Professor Pradipta Biswas, a renowned professor in the CPDM department at the Indian Institute of Science (IISc). The project is generously funded by the Roboter Bosch Cyber-Physical Department of IISc and Tata Consultancy Services (TCS). I was an assistant research fellow for this project, the project is incubated in the Nahar Lab of the Robert Bosch Cyber Physical Systems Department, an incubation initiative established by Professor Pradipta Biswas. I was responsible for the development and implementation of motion planning algorithms crucial for orchestrating precise and efficient robotic movements during task scheduling."

Abstract

Scheduling tasks for multiple robots with diverse capabilities can be challenging. This challenge arises as these robots collaborate under precedence constraints, especially when environmental demands require certain robots to handle heavier workloads. This complexity is compounded when human intervention is needed to allocate limited resources. To address this, we introduce the Demand-Aware multi-Robot Task Scheduling (DARTS) approach, employing a multi-agent multi- armed bandit framework to estimate environmental demand. We conducted a mixed reality based user study to investigate how human perception influences task scheduling and personalize the resource allocation process. To evaluate the effectiveness of our approach, we conducted a comprehensive benchmarking analysis focusing on multi-robot planning and scheduling. Experimental results demonstrate that the proposed DARTS approach outperforms rate-monotonic scheduling and is comparable to state-of-the-art scheduling methods in terms of robot waiting time, task completion time, and demand-aware performance metrics. Our findings of user study indicate that human task schedulers demonstrated improved performance in scenarios involving autonomous agent assistance compared to situations with lesser autonomy of the robotic systems.

Introduction

Multi-robot systems are effective in enhancing task efficiency and scalability by distributing the workload among multiple robots, enabling parallel execution of tasks, and facilitating collaboration and coordination among the robots. In recent years such systems gained popularity due to their potential in various applications such as emergency rescue and care, surveying, manufacturing and logistics as reported by Rajan et al. [1]. Nonetheless, these robotic systems may not possess the robustness to autonomously handle all tasks, necessitating either human involvement within the loop or human supervision, as elucidated by Nahavandi et al. [2]. Achieving efficient task planning, scheduling, motion planning, and control while preserving mission objectives can be intricate, especially in the context of multi-robot systems that involve human intervention, which brings its own set of distinctive challenges. Goodrich et al. [3] explored the spectrum of human-robot interactions and the intricacies within human-supervised and human-in-the loop robotic systems.

In a mixed reality based user study involving eight participants (six male and two female), we investigated the influence of human perception on human-supervised resource allocation. This study encompassed various sce- narios, including independent scheduling, autonomous agent assistance, and simulated scheduling environments. The user study enables us to achieve a deeper understanding of human preferences, facilitating further customization of the resource allocation process. Another significant contribu- tion is the introduction of the Demand-Aware multi-Robot Task Scheduling (DARTS) approach, which addresses multi- robot task scheduling by taking into account environmental demands and precedence constraints, promoting effective collaboration and coordination among robots. Environmental demand estimation is achieved through a multi-agent multi- armed bandit approach, as elucidated by Sandula et al. [4].

In this context, the DARTS approach utilizes the bandit solver to frame the task scheduling problem as a multi-armed bandit problem, considering the precedence constraints among robot coalitions. Human-robot interaction can be classified into two primary categories. The first category is human-in-the-loop (HIL) [5]–[9], where a human operator actively collaborates with or controls the robot during task execution. The second category is human-on-the-loop (HOL) [10]–[12] interaction, where a human operator supervises the task performed by the robotic system. Our research centers on HOL robotic systems, with a particular emphasis on human task scheduling for multi-robot systems.

The literature on robotics has investigated task scheduling in various scenarios for both single [13]–[15] and multi robot [7], [16]–[21] systems. Previous studies have investigated task scheduling for a single and multiple robot task scheduling in applications industrial automation, assembling, and palletizing tasks etc. Dhanaraj et al. [7] have proposed a human-in-the-loop task scheduling with focus on fault recovery. Zhang et al. [21] proposed heuristic based task scheduling approaches for a generalized scenario where robots form a coalition to accomplish a task. However, a human-on-the-loop demand aware scheduling strategy considering the precedence constraints is not investigated in the current literature. Therefore, to address this gap, we introduce a novel approach: DARTS - a Demand-Aware multi-Robot Task Scheduling algorithm. This algorithm leverages a multi-agent multi-armed bandit [22] framework, as elucidated by Sandula et al. [4], to estimate environmental demand.

In brief, our research makes two notable contributions. First, we propose a novel approach known as DARTS (Demand-Aware multi-Robot Task Scheduling) for multi- robot task scheduling. This approach takes into account environmental demand and precedence constraints, and we have conducted a comprehensive benchmarking analysis to evaluate its effectiveness. Second, we have conducted a mixed reality based user study to investigate how human perception influences human-guided task scheduling. We observed that human task schedulers demonstrated improved performance in scenarios involving autonomous agent assis- tance compared to situations with lesser autonomy of the robotic systems.

Probabilities at which tasks have been generated. A central station receives the packages and then transfers them to the pickup points based on the type of packages.

Mixed Reality User Study

I played an Integral Part in devloping the Motion planning algorithms for the Mixed Reality user study but I cannot disclose much about the Algorithm (DARTS) which was used in the navigation of multiple robots in the Task Scheduling Algorithm

fig 3 : Mixed Reality setup for single robot scheduling.
fig 4 : Mixed reality setup for multi-robot scheduling.

We conducted the user study to understand how human perception effects the task scheduling in a human-on-the- loop robotic system. Hence, we used a mixed-reality setup to create a realistic warehouse scenario for a pickup-dispatch task. The user study has three distinct scenarios. These scenarios encompassed (1) Single-robot scheduling, (2) Multi- robot scheduling, and (3) Simulated scheduling with zero robots, each of which is described below. We collected data from all the participants across all the scenarios.

1. Material: We established a mixed reality environment by utilizing Microsoft Hololens [28], Unity [29], Turtlebot [30] and ROS [31] platforms. In this environment, we introduced three distinct scenarios aimed at investigating the influence of human perception on task scheduling.

2. Participants: We enlisted 8 participants (6 males, 2 females) from our university, with an average age of 24.37 years and a standard deviation of 2.99. None of the participants had color blindness, and they all granted the required permissions and consent for the study.

3. Setup: In case 1, known as single-robot scheduling (depicted in Figure 3), participants are assigned the operation of a single robot and tasked with deducing rewards to maximize their collection. Participants control the robots using the virtual buttons, and when a robot reaches a designated station, the reward obtained is revealed in green text atop the station. During this phase, we measure the distance travelled by robot, record task completion times, and calculate the rewards achieved in each iteration. The rewards in each iteration are calculated based on specific probability distributions unique to each station, all of which are kept confidential from the participants. This information remains undisclosed throughout the study. In case 2, known as multi-robot scheduling, as shown in the Figure 4 we introduce an autonomous agent into the environment. Here, participants observe the actions of the autonomous agent and have the option to incorporate its strategies into their own task scheduling. This stage serves to compare participant performance when acting indepen- dently versus when assisted by the autonomous agent. The autonomous agent utilizes the DARTS algorithm for task scheduling. In this environment, two rewards are displayed: one collected by the autonomous agent (yellow colour) and the other by the user-controlled robot. Participants can utilize the reward data of agent to optimize their scheduling processes. In the case 3, referred to as simulated scheduling with zero robots, the mixed reality setup remains identical to the previous cases. However, it lacks physical robots, and participants instantly observe rewards upon interacting with virtual buttons.

4. Design: The user interface, depicted in figures 3 and 4, features five virtual buttons for task scheduling. For cases 1 and 2, each button when pressed, the tele-operated robot executes a pickup-dispatch task. The robot autonomously navigates first to the base location and subsequently to the corresponding station. Upon task completion, a reward is displayed on the respective station. For the tele-operated robot, the reward is shown in green text, while for the autonomous robot, it appears in yellow text. In the simulated scheduling scenario (case 3), rewards are instantly shown on the corresponding station when users press the virtual button, as no robots are involved.

5.Procedure: Participants were briefed about the objectives of the study. Their goal was to maximize rewards. We documented the total reward of each participant, task execution time, and robot travel distance for all scenarios.

Result and Discussion of the User Study

The results of the motion planning algorithm cannot be disclosed as it has not been open sourced so only the Results of the user study is being shared

fig 7 : Reward Analysis
fig 8 : Time Analysis
fig 9 : Distance Analysis

The user study has three distinct conditions: (1) Single- robot (no autonomous Agent), (2) Multi-robot scheduling (with autonomous agent) and (3) Simulated scheduling envi- ronment with no robots as explained in Section III-C. In total, each participant was responsible for scheduling 45 tasks: 15 tasks independently in case 1, 15 tasks with the assistance of the autonomous agent in case 2 and additionally, participants completed 15 tasks in a simulated environment where there was no robot involved, and the reward was instantly observed by the user.

Our analysis encompassed three distinct aspects It may be noted from figures 7 and 9, it becomes evident that users generally prioritized lower rewards as a means to minimize the overall distance traveled by the robots, particularly in case 1. The exception to this trend was user 4. However, in scenarios where scheduling involved au- tonomous agent assistance, users exhibited improved perfor- mance in terms of rewards and seemed less concerned about the distance traveled by the robots. Additionally, we noted that there was no substantial difference in user performance regarding rewards between cases 1 and 3. From Figure 8, it is clear that participants favored com- pleting tasks quickly over optimal scheduling in independent scheduling (Case 1). However, in Case 2, with autonomous agent assistance, participants took more time to complete tasks while achieving higher rewards. Figure 9 reveals scheduling preferences of the participants. In case 1, they sought to minimize the travel distance of robot, deeming it efficient. In contrast, Case 2 presented a different scenario. Here, the autonomous agent employed the DARTS algorithm. Participants shifted their focus to- ward maximizing rewards. They made this adjustment after observing the rewards acquired by the autonomous agent, even if it meant the robot had to cover a greater distance.Remarkably, in case 2, the robot covered significantly more distance compared to case 1, except for user 4.

We performed a one-way ANOVA to compare the total rewards of users across three cases: 1, 2, and 3. This analysis did not reveal any statistically significant differences. However, when we performed paired T-tests on other dependent variables, namely total task completion time and total distance traveled by the tele-operated robot, we observed statistical significance among the cases 1 and 2. A paired T-test score for total task completion time indicates that the users took more time to complete the tasks in case 2, while case 1 is significantly lower ( \(t = -4.693, p < 0.050, Cohen's d = -1.369\) ) than case 2. The paired T-test score for total distance traveled by the tele-operated robot indicates that the tele-operated robot traveled a significantly longer distance to complete the tasks in case 2, while case 1 is significantly lower ( \(t = -2.759, p < 0.050, Cohen's d = -0.787\) ) than case 2. In conclusion, the data suggests that there are significant differences between the means of distances traveled by the tele-operated robot and the time taken by users across the different cases.

In summary, participants initially prioritized task comple- tion speed and minimizing travel distance when scheduling tasks independently. However, when an autonomous agent was introduced, task scheduling improved, resulting in higher rewards but with increased time consumption. Participants also learned that minimizing robot travel distance did not always yield the best task scheduling outcomes, a finding supported by statistical analysis.

Future Work and Conclusion

Extensive benchmarking demonstrated that DARTS performed competitively with state-of-the-art algorithms and outperformed the rate-monotonic scheduling approach in terms of demand-aware performance [4], task completion times, and robot waiting times. The mixed reality user study emphasized the benefits of integrating an autonomous agent into human-on-the-loop multi-robot task scheduling. Future work will focus on demand-aware multi- robot task allocation with human supervision.

References

1. Rajan, J., Shriwastav, S., Kashyap, A., Ratnoo, A. and Ghose, D., 2021. Disaster management using unmanned aerial vehicles. In Unmanned Aerial Systems (pp. 129-155). Academic Press.
2. Nahavandi, S., 2017. Trusted autonomy between humans and robots: Toward human-on-the-loop in robotics and autonomous systems. IEEE Systems, Man, and Cybernetics Magazine, 3(1), pp.10-17.
3. Goodrich, M.A. and Schultz, A.C., 2008. Human–robot interaction: a survey. Foundations and Trends® in Human–Computer Interaction, 1(3), pp.203-275.
4. AK Sandula, A Khokhar, D Ghose and P Biswas "Demand-Aware Multi-Robot Task Scheduling with Mixed Reality Simulation," 2023 32nd IEEE International Conference on Robot and Human Interactive Communication (RO-MAN), Busan, South Korea, 2023.
5. Papallas, R. and Dogar, M.R., 2020, May. Non-prehensile manipulation in clutter with human-in-the-loop. In 2020 IEEE International Conference on Robotics and Automation (ICRA) (pp. 6723-6729). IEEE.
6. Manyar, O.M., McNulty, Z., Nikolaidis, S. and Gupta, S.K., 2023, May. Inverse Reinforcement Learning Framework for Transferring Task Sequencing Policies from Humans to Robots in Manufacturing Applications. In 2023 IEEE International Conference on Robotics and Automation (ICRA) (pp. 849-856). IEEE.
7. Dhanaraj, N., Narayan, S.V., Nikolaidis, S. and Gupta, S.K., 2023, May. Contingency-Aware Task Assignment and Scheduling for Human-Robot Teams. In 2023 IEEE International Conference on Robotics and Automation (ICRA) (pp. 5765-5771). IEEE.
8. Ng, E., Liu, Z. and Kennedy, M., 2023, May. It takes two: Learning to plan for human-robot cooperative carrying. In 2023 IEEE International Conference on Robotics and Automation (ICRA) (pp. 7526-7532). IEEE.
9. Ford, C.J., Li, H., Lloyd, J., Catalano, M.G., Bianchi, M., Psomopoulou, E. and Lepora, N.F., 2023. Tactile-Driven Gentle Grasping for Human-Robot Collaborative Tasks. arXiv preprint arXiv:2303.09346.
10. Sheridan, T.B., 2021. Human supervisory control of automation. Handbook of Human Factors and Ergonomics, pp.736-760.
11. Al-Hussaini, S., Gregory, J.M. and Gupta, S.K., 2023. Generating Task Reallocation Suggestions to Handle Contingencies in Human-Supervised Multi-Robot Missions. IEEE Transactions on Automation Science and Engineering.
12. Al-Hussaini, S., Gregory, J.M., Guan, Y. and Gupta, S.K., 2020, October. Generating alerts to assist with task assignments in human-supervised multi-robot teams operating in challenging environments. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 11245-11252). IEEE.
13. Stavridis, S. and Doulgeri, Z., 2018, October. Bimanual assembly of two parts with relative motion generation and task-related optimization. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 7131-7136). IEEE.
14. Mendez, J.B., Perez-Vidal, C., Heras, J.V.S. and Pérez-Hernández, J.J., 2020. Robotic pick-and-place time optimization: Application to footwear production. IEEE Access, 8, pp.209428-209440.
15. Szczepanski, R., Erwinski, K., Tejer, M., Bereit, A. and Tarczewski, T., 2022. Optimal scheduling for palletizing task using robotic arm and artificial bee colony algorithm. Engineering Applications of Artificial Intelligence, 113, p.104976.
16. Ho, Y.C. and Liu, H.C., 2006. A simulation study on the performance of pickup-dispatching rules for multiple-load AGVs. Computers industrial engineering, 51(3), pp.445-463.
17. Kalempa, V.C., Piardi, L., Limeira, M. and de Oliveira, A.S., 2021. Multi-Robot preemptive task scheduling with fault recovery: A novel approach to automatic logistics of smart factories. Sensors, 21(19), p.6536.
18. Kousi, N., Koukas, S., Michalos, G. and Makris, S., 2019. Scheduling of smart intra–factory material supply operations using mobile robots. International Journal of Production Research, 57(3), pp.801-814.
19. Gao, T., Tian, Y. and Bhattacharya, S., 2021, September. Refuel scheduling for multi-robot charging-on-demand. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 5825-5830). IEEE.
20. Bischoff, E., Meyer, F., Inga, J. and Hohmann, S., 2020, October. Multi-robot task allocation and scheduling considering cooperative tasks and precedence constraints. In 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC) (pp. 3949-3956). IEEE.
21. Zhang, Y. and Parker, L.E., 2013, May. Multi-robot task scheduling. In 2013 IEEE International Conference on Robotics and Automation (pp. 2992-2998). IEEE.
22. Lattimore, T. and Szepesvari, C., 2020. Bandit algorithms. Cambridge University Press.
23. Gerkey, B.P. and Mataric, M.J., 2002. Sold!: Auction methods for multirobot coordination. IEEE transactions on robotics and automation, 18(5), pp.758-768.
24. Hart, P., Nilsson, N. Raphael, B., 1968. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), pp.100–107. Available at: https://doi.org/10.1109/tssc.1968.300136.
25. Sharon, G., Stern, R., Felner, A. and Sturtevant, N.R., 2015. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219, pp.40-66.
26. Barer, M., Sharon, G., Stern, R. and Felner, A., 2014. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In Proceedings of the International Symposium on Combinatorial Search (Vol. 5, No. 1, pp. 19-27).
27. Krishna, C.M. and Shin, K.G., 1997. Real-time systems. McGraw-Hill series in computer science.
28. Microsoft HoloLens. [online] learn.microsoft.com. Available at: https://learn.microsoft.com/en-us/hololens/.
29. Unity Technologies (2019). Unity. [online] Unity. Available at: https://unity.com/.
30. TurtleBot3 (2020). ROBOTIS [online] Available at: https://www.turtlebot.com/turtlebot3/.
31. ROS (2020). ROS.org — Powering the world’s robots. [online] Ros.org. Available at: https://www.ros.org/.